let _ = require('lodash');
//生成一个具有唯一解的数独谜题
function makepuzzle(board) {
	let puzzle  = []; //存储谜题中的已知数字
	let deduced = makeArray(81, null);   //记录已确定的数字位置
	let order   = _.range(81);

	shuffleArray(order);  //随机打乱顺序

	//填充已知数字
	for (let i = 0; i < order.length; i++) {
		let pos = order[i];

		if (deduced[pos] == null) {
			puzzle.push({pos:pos, num:board[pos]});
			deduced[pos] = board[pos];
			deduce(deduced); //尝试根据当前已知的数字推理出其他可以确定的数字
		}
	}

	shuffleArray(puzzle);  //打乱 puzzle 数组中的元素顺序，确保谜题中的已知数字位置也是随机的
	
	//最终返回由 puzzle 中的已知数字生成的数独谜题布局
	return boardforentries(puzzle);
}

//用于根据数独谜题的难度生成数独
function ratepuzzle(puzzle, level) {
	let answer = solvepuzzle(puzzle);
	let add = 0;
	let index = _.range(81);
	shuffleArray(index);

	if(level ==  1) {
		add = 30;
	} else if (level == 2) {
		add = 15;
	} else {
		add = 0;
	}
	
	for(let i = 0 ; i < index.length ; i++){
		let pos = index[i];
		if(puzzle[pos] == null) {
			puzzle[pos] = answer[pos];
			add--;
		}
		if(add <= 0) {
			break;
		}
	}
	
	return puzzle;
}

function solvepuzzle(board) {
    return solveboard(board).answer;
}

//用于解决数独问题
function solveboard(original) {
	let board   = [].concat(original); //浅拷贝,确保不会直接修改原始数组
	let guesses = deduce(board);

	if (guesses == null) {
		return {state:[], answer:board};
	}

	let track = [{guesses:guesses, count:0, board:board}];
	return solvenext(track);
}

//通过回溯法逐步尝试不同的猜测以求解数独
function solvenext(remembered) {
    while (remembered.length > 0) {
    	let tuple1 = remembered.pop();

    	if (tuple1.count >= tuple1.guesses.length) {
    		continue;
    	}
 
    	remembered.push({guesses:tuple1.guesses, count:tuple1.count+1, board:tuple1.board});
    	let workspace = [].concat(tuple1.board);
    	let tuple2    = tuple1.guesses[tuple1.count];

    	workspace[tuple2.pos] = tuple2.num;

    	let guesses = deduce(workspace);

    	if (guesses == null) {
	    	return {state:remembered, answer:workspace};
	    }

    	remembered.push({guesses:guesses, count:0, board:workspace});
	}

    return {state:[], answer:null};
}

//通过直接冲突填充和消除法填充逐步求解数独谜题
//如果遇到无法确定的情况，则通过猜测和回溯继续求解。最终返回一个猜测列表或空数组表示无解
function deduce(board) {
	while (true) {  //循环直至数独填满或无解返回空数组
		let stuck = true;  //标记当前是否陷入僵局，即没有明显的下一步可以进行填充。初始值为 true，表示尚未找到可确定的填充位置。
		let guess = null;  //存储可能的猜测列表，用于后续的猜测和回溯。初始值为 null，表示尚未生成任何猜测。
		let count = 0;  //记录猜测的数量或次数，辅助选择最优猜测路径。初始值为 0，表示尚未进行任何猜测。

	    // fill in any spots determined by direct conflicts
	    let tuple1  = figurebits(board);  //获取每个位置允许的数字和需要填入的数字
	    let allowed = tuple1.allowed;   //每个位置允许的数字（以位掩码形式表示）
	    let needed  = tuple1.needed;  //每个行、列、宫需要填入的数字（以位掩码形式表示）

	    for (let pos = 0; pos < 81; pos++) {
	    	if (board[pos] == null) {
	    		let numbers = listbits(allowed[pos]);  //获取当前位置允许的数字列表
	    		if (numbers.length == 0) {
	    			return [];  //如果没有允许的数字，返回空数组表示无解
	    		}
	    		else if (numbers.length == 1) {
	    			board[pos] = numbers[0];  //如果只有一个允许的数字，直接填充
	    			stuck = false;  //标记有进展，未陷入僵局
	    		}
	    		else if (stuck == true) {  //如果有多个允许的数字且当前陷入僵局
	    			let t = _.map(numbers, function(val, key) {
	    				return {pos:pos, num:val};   //记录所有可能的猜测
	    			});

	    			let tuple2 = pickbetter(guess, count, t);  //选择最优猜测路径
	    			guess = tuple2.guess;
	    			count = tuple2.count;
	    		}
	    	}
	    }

		//如果有进展（stuck == false），重新计算每个位置允许的数字和需要填入的数字
	    if (stuck == false) {
		    let tuple3  = figurebits(board);
		    allowed = tuple3.allowed;
		    needed  = tuple3.needed;
	    }

    	// fill in any spots determined by elimination of other locations
		//消除法填充
    	for (let axis = 0; axis < 3; axis++) { //按行、列、宫检查
	    	for (let x = 0; x < 9; x++) {
        		let numbers = listbits(needed[axis * 9 + x]); //对于每个行、列、宫，获取需要填入的数字列表 numbers

		    	for (let i = 0; i < numbers.length; i++) { 
		    		let n     = numbers[i];
		            let bit   = 1 << n;
          			let spots = [];
					//对于每个需要填入的数字 n，找到所有可能的位置 spots
			    	for (let y = 0; y < 9; y++) {
			    		let pos = posfor(x, y, axis);
			    		if (allowed[pos] & bit) {
				    		spots.push(pos);
				    	}
			    	}

			    	if (spots.length == 0) {
				    	return [];  //如果没有可能的位置，返回空数组 [] 表示无解
				    }
				    else if (spots.length == 1) {
					    board[spots[0]] = n;  //如果只有一个可能的位置，直接填充并标记有进展 (stuck = false)
					    stuck = false;
					}
					else if (stuck) {  //如果有多个可能的位置且当前陷入僵局
		    			let t = _.map(spots, function(val, key) {
		    				return {pos:val, num:n};
		    			});

		    			let tuple4 = pickbetter(guess, count, t);
		    			guess = tuple4.guess;
		    			count = tuple4.count;
					}
		    	}
	    	}
    	}

    	if (stuck == true) {
    		if (guess != null) {   //如果陷入僵局且有猜测列表
    			shuffleArray(guess);  //打乱猜测顺序并返回
    		}

    		return guess;
    	}
	}
}

//根据当前的游戏板状态，计算出每个位置可以填写的数字组合（allowed），以及每个轴上缺失的数字组合（needed）。
function figurebits(board) {
	let needed  = []; //用于存储每个轴上缺失的数字组合。
	//如果 board 中某个位置是 null 或未填，则对应的 allowed 位置设为 511
	//如果 board 中某个位置已有数字，则对应的 allowed 位置设为 0（表示该位置不能再填任何数字）
	let allowed = _.map(board, function(val, key) {
		return val == null ? 511 : 0;   //511（二进制 111111111，表示所有数字 1-9 都可能）
	}, []);  

	//axis 变量从 0 到 2，分别代表行、列和宫（3x3 的小方块）
	for (let axis = 0; axis < 3; axis++) {
		for (let x = 0; x < 9; x++) {
			let bits = axismissing(board, x, axis);
			needed.push(bits);

		    for (let y = 0; y < 9; y++) {
		    	let pos = posfor(x, y, axis);
		        allowed[pos] = allowed[pos] & bits;
			}
		}
	}

	return {allowed:allowed, needed:needed};
}

//根据传入的参数 x, y 和 axis 计算并返回一个位置索引
function posfor(x, y, axis) {
	if (axis == undefined) { axis = 0; }

    if (axis == 0) {  //按行优先排列的二维数组
	    return x * 9 + y;
	}
	else if (axis === 1) { //按列优先排列的二维数组
		return y * 9 + x;
	}
	//其他情况（九宫格布局）
	//第一个数组 [0, 3, 6, 27, 30, 33, 54, 57, 60] 对应九宫格中每个小方块的起始位置（即左上角元素的索引），x 表示选择哪个小方块
	//第二个数组 [0, 1, 2, 9, 10, 11, 18, 19, 20] 对应每个小方块内部的相对位置，y 表示选择小方块内的具体位置
	return ([0,3,6,27,30,33,54,57,60][x] + [0,1,2,9,10,11,18,19,20][y])
}

function axisfor(pos, axis) {
	if (axis == 0) {
		return Math.floor(pos / 9);
	}
	else if (axis == 1) {
		return pos % 9;
	}

	return Math.floor(pos / 27) * 3 + Math.floor(pos / 3) % 3;
}

//计算数独游戏中某一行、列或宫中缺失的数字
//返回的结果是一个整数，其二进制表示中为1的位表示缺失的数字
function axismissing(board, x, axis) {
	let bits = 0;  //用于记录已存在的数字,每个数字对应一个二进制位

	for (let y = 0; y < 9; y++) {
		let e = board[posfor(x, y, axis)];

		//如果单元格中有数字（即 e 不为 null），则将 bits 中对应的位设置为1
		//例如，如果 e 是3，则执行 bits |= 1 << 3，这会将 bits 的第4位（从0开始计数）设置为1
		if (e != null) {
			bits |= 1 << e;
		}
	}

	//使用异或运算 ^ 计算缺失的数字
	//例如，如果 bits 是 111111011，表示数字8缺失，则 511 ^ bits 的结果是 000000100，即数字8
	return 511 ^ bits;
}

//返回包含所有位为 1 的索引的数组
function listbits(bits) {
    var list = [];
	for (var y = 0; y < 9; y++) {
		if ((bits & (1 << y)) != 0) {
			list.push(y);
		}
	}

  return list;
}

//用于在两个选项中选择一个更优的猜测，并返回包含猜测和计数的对象
// TODO: make sure callers utilize the return value correctly
function pickbetter(b, c, t) {
	if (b == null || t.length < b.length) {
		return {guess:t, count:1};
	}
	else if (t.length > b.length) {
		return {guess:b, count:c};
	}
	else if (randomInt(c) == 0) {
		return {guess:t, count:c+1};
	}

	return {guess:b, count:c+1};
}

//根据输入的 entries 数组生成一个包含 81 个元素的数独棋盘数组 board
function boardforentries(entries) {
	var board = _.map(_.range(81), function(val, key) {
		return null;
	});

	for (var i = 0; i < entries.length; i++) {
		var item = entries[i];
		var pos  = item.pos;
		var num  = item.num;

		board[pos] = num;
	}

	return board;
}


//用于生成一个0到max之间（包括max）的随机整数
function randomInt(max) {
	return Math.floor(Math.random() * (max+1));
}

//打乱数组元素的顺序
function shuffleArray(original) {
	// Swap each element with another randomly selected one.
    for (let i = 0; i < original.length; i++) {
        let j = i;
        while (j == i) {
            j = Math.floor(Math.random() * original.length);
        }
        let temp = original[i];
        original[i]  = original[j];
        original[j]  = temp;
    }
}


function makeArray(length, value) {
	return _.map(_.range(length), function(val, key) {
		return value;
	})
}

module.exports = {
	makepuzzle  : function () { return makepuzzle(solvepuzzle(makeArray(81, null))); }, //生成一个具有唯一解的数独谜题。
	solvepuzzle : solvepuzzle,  //解决数独问题，返回答案
	ratepuzzle  : ratepuzzle,  //评估数独谜题的难度
	posfor      : posfor,  //根据传入的参数计算并返回一个位置索引
};
